
def maxProfit(prices):  # 买卖股票最佳时间,需要一个最小值mins来标注某一天之前股票的最小值。需要maxs标注到目前为止能够赚到的最多钱
    if len(prices) <= 1:
        return 0

    mins = prices[0]
    maxs = 0
    for i in prices:
        mins = min(mins, i)
        maxs = max(i - mins,maxs)

    return maxs

def maxProfitII(prices):
    sum = 0

    if len(prices) <= 1:
        return 0
    for i in range(len(prices) - 1):
        if prices[i + 1] > prices[i]:
            sum = sum + prices[i + 1] - prices[i]
    return sum

# 这个在买卖过程中考虑到交易费用，最值一般没有头绪时考虑动态规划,最重要的状态转移方程
# 未优化内存
def maxProfitFee1(prices,fee):   # prices为股票价格，fee为交易费用
    dp = [[0, -prices[0]]] + [[0,0]] * (len(prices) - 1)
    for i in range(1, len(prices)):
        dp[i][0] = max(dp[i-1][0], dp[i-1][1] + prices[i] - fee)
        dp[i][1] = max(dp[i-1][1], dp[i-1][0] - prices[i])
    return dp[len(prices) - 1][0]


# 优化内存
def maxProfitFee(prices,fee):   # prices为股票价格，fee为交易费用
    dp0 = 0 # 某一天没有股票的最大收益(初始化为0)
    dp1 = -prices[0] # 某一天有股票具有的最大收益(初始化为-price)
    for i in range(1, len(prices)):
        temp = dp0
        dp0 = max(dp0, dp1 -fee + prices[i])
        dp1 = max(dp1, temp -prices[i])
    return dp0  # 最大值一定是最后一天没有股票的情况


# 贪心算法
def maxProfixTanXin(prices,fee):
    buy = prices[0] + fee
    profit = 0
    for i in range(1, len(prices)):
        if prices[i] + fee < buy:
            buy = prices[i] + fee
        elif prices[i] > buy:
            profit = profit + prices[i] - buy
            buy = prices[i] # 假的卖出操作，后面数值在增加时依然可以进行卖出操作
    return profit
